#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <string.h>
#include <sys/queue.h>

/*********************** 定义节点类型(放置到头文件) ***********************/
typedef struct _mynode mynode_t;
#if 0
struct _mynode{
	uint32_t	key;
	/* ... */
	struct {
		struct _mynode *stqe_next;	/* next element */
	}	tailq_entry;
};
#else
struct _mynode{
	uint32_t	key;
	/* ... */
	TAILQ_ENTRY(_mynode)	tailq_entry;
};
#endif


/************************** 定义链表头(myhead) **************************/
#if 0
struct tailq_head {
	struct _mynode *tqh_first;		/* first element */
	struct _mynode **tqh_last;	/* addr of last next element */
}	myhead;
#else
TAILQ_HEAD(tailq_head, _mynode)   myhead;
#endif

//pthread_mutex_t tailq_lock = PTHREAD_MUTEX_INITIALIZER;

/* *********************************************************************
	初始化一个链表
***********************************************************************/
void tailq_init(void)
{
#if 0
	do {
		(&myhead)->tqh_first = NULL;
		(&myhead)->tqh_last = &(&myhead)->tqh_first;
	} while (/*CONSTCOND*/0);
#else
	TAILQ_INIT(&myhead);
#endif
}

/* *********************************************************************
	从链表中把首次出现key的节点(mynode_t)出队，函数只负责出队，用完之后请记得free掉
***********************************************************************/
mynode_t* tailq_dequeue(uint32_t key)
{
	mynode_t *node = NULL;
	
	//pthread_mutex_lock(&tailq_lock);
	TAILQ_FOREACH(node, &myhead, tailq_entry) {
		if(node->key == key)
			break;
	}
	
	if(node) {
		TAILQ_REMOVE(&myhead, node, tailq_entry);
	}
	//pthread_mutex_unlock(&tailq_lock);
	
	return node;
}

/* *********************************************************************
	把节点(mynode)入队到队尾，函数把节点的副本进行入队。
	如果传进来的mynode是malloc的指针，函数返回之后请注意free掉
***********************************************************************/
mynode_t* tailq_enqueue(mynode_t* mynode)
{
	mynode_t *node = NULL;
	
	if(!mynode){
		printf("FAILED:mynode is NULL\n");
		return NULL;
	}
	
	//为什么要malloc+memcpy？(避免别人把一个局部变量的指针传进newtask导致内存泄漏)
	node = (mynode_t *)malloc(sizeof(mynode_t));
	if(!node){
		printf("FAILED:malloc node(NULL)\n");
		return NULL;
	}
	memset(node, 0, sizeof(mynode_t));
	memcpy(node, mynode, sizeof(mynode_t));
	
	//pthread_mutex_lock(&tailq_lock);
#if 0
	do {
	(node)->tailq_entry.tqe_next = NULL;
	(node)->tailq_entry.tqe_prev = (&myhead)->tqh_last;
	*(&myhead)->tqh_last = (node);
	(&myhead)->tqh_last = &(node)->tailq_entry.tqe_next;
	} while (/*CONSTCOND*/0);
#else
	TAILQ_INSERT_TAIL(&myhead, node, tailq_entry);
#endif
	//pthread_mutex_unlock(&tailq_lock);
    
	return node;
}

int main(void)
{
	mynode_t newnode;
	mynode_t	*node = NULL,
				*nodea = NULL,
				*nodeb = NULL,
				*nodec = NULL,
				*noded = NULL;
	
	//初始化一个链表
	tailq_init();
	
	//在队列末尾插入1
	newnode.key = 1;
	tailq_enqueue(&newnode);
	
	//在队列末尾插入2
	newnode.key = 2;
	tailq_enqueue(&newnode);
	
	//在队列末尾插入3
	newnode.key = 3;
	tailq_enqueue(&newnode);
	
	//在队列末尾插入4
	newnode.key = 4;
	tailq_enqueue(&newnode);
	
	//在队列末尾插入5
	newnode.key = 5;
	tailq_enqueue(&newnode);
	
	/* 遍历队列 */
	TAILQ_FOREACH(node, &myhead, tailq_entry) {
		printf("node->key = %d\n", node->key);
	}
	puts("");

	//出队结点
	node = tailq_dequeue(4);
	if(node)	free(node);
	node = tailq_dequeue(5);
	if(node)	free(node);
	node = tailq_dequeue(1);
	if(node)	free(node);
	node = tailq_dequeue(3);
	if(node)	free(node);
	node = tailq_dequeue(2);
	if(node)	free(node);
	node = tailq_dequeue(1);
	if(node)	free(node);
	
	//在队列末尾插入5(两个)
	newnode.key = 5;
	tailq_enqueue(&newnode);
	nodea = tailq_enqueue(&newnode);
	
	//在结点nodea后面插入nodeb(6)
	nodeb = (mynode_t *)malloc(sizeof(mynode_t));
	nodeb->key = 6;
    TAILQ_INSERT_AFTER(&myhead, nodea, nodeb, tailq_entry);
	
	//在结点nodea前面面插入nodec(4)
	nodec = (mynode_t *)malloc(sizeof(mynode_t));
	nodec->key = 4;
    TAILQ_INSERT_BEFORE(nodea, nodec, tailq_entry);
	
	//在队头加入noded(1)
	noded = (mynode_t *)malloc(sizeof(mynode_t));
	noded->key = 1;
	TAILQ_INSERT_HEAD(&myhead, noded, tailq_entry);
	
	/* 遍历队列 */
	TAILQ_FOREACH(node, &myhead, tailq_entry) {
		printf("node->key = %d\n", node->key);
	}
	puts("");
	
	
	printf("正序遍历尾队列\n");
	printf("方法一\n");
	TAILQ_FOREACH(node, &myhead, tailq_entry) {
		printf("node->key = %d\n", node->key);
	}
	puts("");
	printf("方法二\n");
	for (node = TAILQ_FIRST(&myhead); node; node = TAILQ_NEXT(node, tailq_entry)) {
		printf("node->key = %d\n", node->key);
	}
	puts("");
	
	
	printf("逆序遍历尾队列\n");
	printf("方法一\n");
	TAILQ_FOREACH_REVERSE(node, &myhead, tailq_head, tailq_entry) {
		printf("node->key = %d\n", node->key);
	}
	puts("");
	printf("方法二\n");
	for (node = TAILQ_LAST(&myhead, tailq_head); node; node = TAILQ_PREV(node, tailq_head, tailq_entry)) {
		printf("node->key = %d\n", node->key);
		TAILQ_REMOVE(&myhead, node, tailq_entry);  
		free(node);  
	}  

	if (TAILQ_EMPTY(&myhead)) {  
		printf("the tail queue is empty now.\n");     
	}
	
    exit(EXIT_SUCCESS);
}

